package org.algorithm.wE1.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Test;

import java.util.Arrays;

/**
 * @Date 2022/2/25
 * @Link {https://leetcode-cn.com/problems/next-greater-node-in-linked-list/}
 */
public class 链表中下一个最大的节点 {


    @Test
    public  void  test(){
        int[] ints = nextLargerNodes(ListNode.build(1, 7, 5, 1, 9, 2, 5, 1));
        System.out.println("ints = " + Arrays.toString(ints));
    }

    public int[] nextLargerNodes(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return new int[]{0};
        }
        int len = 0;
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        //获取链表的长度
        while (head!=null){
            head = head.next;
            len++;
        }
        head = dummyNode.next;
        int[] arr = new int[len];
        int m =0;
        while (head!=null){
            arr[m] = head.val;
            m++;
            head = head.next;
        }
        ListNode slow = dummyNode.next;
        ListNode fast = dummyNode.next;
        int k = 0;
        while (slow!=null){
            if(fast.next!=null&&slow.val<fast.val){
                slow = fast;
            }
            fast = fast.next;
            if(fast == null){
                for (int i = k ; i <arr.length ; i++) {
                    if(arr[i] >= slow.val){
                        arr[i] = 0;
                        k++;
                        break;
                    }
                    if(arr[i]<slow.val){
                        arr[i] = slow.val;
                        k=i+1;
                    }
                }
                slow = slow.next;
                fast = slow;
            }
        }
        return arr;
    }
}
